import java.util.Arrays;

public class Sort {
    public static void merge(int[] q,int l, int r){
        if(l >= r) return;
        int mid = l+r>>1;
        merge(q,l,mid);
        merge(q,mid+1,r);
        int i = l;
        int j = mid+1;
        int k = 0;
        int[] temp = new int[r-l+1];
        while(i <= mid && j <= r){
            if(q[i] <= q[j]) temp[k++] = q[i++];
            else temp[k++] = q[j++];
        }
        while(i <= mid){
            temp[k++] = q[i++];
        }
        while (j <= r){
            temp[k++] = q[j++];
        }
        for(i = l,j = 0;i<=r;i++,j++){
            q[i] = temp[j];
        }
    }

    public static void main(String[] args) {
        int[] arr = new int[]{1,3,5,2,4,6};
        System.out.println(Arrays.toString(arr));
        merge(arr,0,5);
        System.out.println(Arrays.toString(arr));
    }
    public static void qsort(int[] q,int l, int r){
        if(l >= r) return;
        int x = q[l+r>>1];
        int i = l-1;
        int j = r+1;
        while(i < j){
            do i++;while(q[i] < x);
            do j--;while(q[j] > x);
            if(i < j) {
                int temp = q[i];
                q[i] = q[j];
                q[j] = temp;
            }
        }
        qsort(q,l,j);
        qsort(q,j+1,r);
    }

    public static void main1(String[] args) {
        int[] arr = new int[]{1,3,5,2,4,6};
        System.out.println(Arrays.toString(arr));
        qsort(arr,0,5);
        System.out.println(Arrays.toString(arr));
    }
}
